package myself.a008CodingTest;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/25
 * Time 21:49
 * Mail 739153436@qq.com
 */
public class SmallerEqualBigger {
    // 笔试用
    public static Node listPartition1(Node head, int pivot) {
        if (head == null) {
            return head;
        }
        // 建立数组
        int length = 0;
        Node cur = head;
        while (cur != null) {
            cur = cur.next;
            length++;
        }

        Node[] arr = new Node[length];
        cur = head;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = cur;
            cur = cur.next;
        }

        // 荷兰国旗
        int pre = -1;
        int last = arr.length;
        int index = 0;
        while (index < last && index < arr.length) {
            if (arr[index].value < pivot) {
                swap(arr, ++pre, index++);
            } else if (arr[index].value == pivot) {
                index++;
            } else if (arr[index].value > pivot) {
                swap(arr, --last, index);
            }
        }

        // 生成链表
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i].next = arr[i + 1];
        }
        arr[arr.length - 1].next = null; // 非常容易发生错误，因为这里不处理的话会形成环形链表
        return arr[0];
    }

    public static void swap(Node[] nodeArr, int a, int b) {
        Node tmp = nodeArr[a];
        nodeArr[a] = nodeArr[b];
        nodeArr[b] = tmp;
    }

    // 面试用
    public static Node listPartition2(Node head, int pivot) {
        if (head == null) {
            return head;
        }
        Node smallHead = null;
        Node smallTail = null;
        Node equalHead = null;
        Node equalTail = null;
        Node bigHead = null;
        Node bigTail = null;

        // 遍历
        Node next = null;
        while (head != null) {
            next = head.next;
            if (head.value < pivot) {
                if (smallHead == null) {
                    smallHead = head;
                    smallTail = head;
                    smallHead.next = null; // 容易踩坑，这里需要将目标置空，否则在拼接的过程中容易产生环
                    smallTail.next = null;
                } else if (smallHead != null) {
                    smallTail.next = head;
                    smallTail = head;
                    smallTail.next = null;
                }
            }
            if (head.value == pivot) {
                if (equalHead == null) {
                    equalHead = head;
                    equalTail = head;
                    equalHead.next = null;
                    equalTail.next = null;
                } else if (equalHead != null) {
                    equalTail.next = head;
                    equalTail = head;
                    equalTail.next = null;
                }
            }
            if (head.value > pivot) {
                if (bigHead == null) {
                    bigHead = head;
                    bigTail = head;
                    bigHead.next = null;
                    bigTail.next = null;
                } else if (bigHead != null) {
                    bigTail.next = head;
                    bigTail = head;
                    bigTail.next = null;
                }
            }
            head = next;
        }

        // 连接
        if (smallHead != null) {
            head = smallHead;
            if (equalHead != null) {
                smallTail.next = equalHead;
                equalTail.next = bigHead;
            } else {
                smallTail.next = bigHead;
            }
        } else if (equalHead != null) {
            head = equalHead;
            equalTail.next = bigHead;
        } else {
            head = bigHead;
        }
        return head;
    }

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }
}
